package com.zjj.lbw.interview.funmath;

/**
 * @author zhanglei.zjj
 * @description 排列硬币-基于迭代|二分查找|牛顿迭代
 * @date 2023/9/1 22:13
 */
public class ArrangeCoins {
    /**
     * 基于迭代
     * @param n
     * @return
     */
    public static int arrangeCoins1(int n) {
        for (int i = 1; i <= n; i++) {
            // 剩余的硬币数量
            n = n - i;
            // 下一列需要的硬币数量，一定是 i + 1，如果能排下一列，剩余硬币 n必须大于 i
            if (n <= i) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 基于二分查找
     * @param n
     * @return
     */
    public static int arrangeCoins2(int n) {
        int low = 1, high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int cost = ((mid + 1) * mid) / 2;
            if (cost == n) {
                return mid;
            } else if (cost > n) {
                high = mid -1;
            } else if (cost < n) {
                low = mid + 1;
            }
        }
        return high;
    }

    /**
     * 基于牛顿迭代
     * @param n
     * @return
     */
    public static int arrangeCoins3(int n) {
        return (int) sqrt(n, n);
    }

    private static double sqrt(double x, int n) {
        double mid = (x + (2 * n - x) / x) / 2;
        if (x == mid) {
            return (int) mid;
        } else {
            return sqrt(mid, n);
        }
    }

    public static void main(String[] args) {
        System.out.println(arrangeCoins1(27));
        System.out.println(arrangeCoins2(27));
        System.out.println(arrangeCoins3(27));
    }
}
